In an information network, an apparatus for transferring a packet, such as a router and a layer 2 switch (L2SW), performs the control of output traffic called “packet-shaping processing”.
In the packet-shaping processing, a transmission rate of a packet flow is smoothened by adjusting the intervals of transmitting packets based on a bandwidth contracted with a user so that an actually-used bandwidth does not exceed the contracted bandwidth. In an apparatus that performs the packet-shaping processing, packets are temporarily stored in a queue (logical queue) provided for each of users, read out from the queue, and transmitted from the apparatus at a predetermined transmission rate. Hereinafter, the above predetermined transmission rate will be also expressed as “a shaping rate”, and packets on which packet-shaping processing has been performed will be also expresses as “shaped packets”. Therefore, “a shaping rate” means a transmission rate at which “shaped packets” are transmitted from the apparatus.
When an output rate at which packets are outputted from the apparatus is higher than an input rate at which packets are inputted to the apparatus, arriving packets are stored in a queue provided for the apparatus. When the length of the queue exceeds a predetermined value called a discard threshold value, a newly arriving packets are discarded without being stored in the queue (this queue management algorithm is called “Tail Drop”).
In order to allow a queue to have tolerance to the bursty arrival of packets, a certain queue length of a buffer area may be reserved for each of the queues. However, when the buffer area having a queue length equal to or larger than the discard threshold value is statically reserved for each of user queues, a usage efficiency of the user queues becomes low, causing limitation on the implementation of the user queues.
For this reason, a common buffer scheme is used in general. The common buffer scheme is a scheme in which a common buffer space (pool) is prepared in addition to the buffer spaces used for the individual user queues. When the total size of arriving packets exceeds a buffer space prepared for an individual user queue, a necessary amount of buffer space is dynamically acquired from the common buffer space. This improves the usage efficiency of the user queues, reducing the total size of the user queues to be implemented.
Further, a technique has been proposed in which received data is stored in the common buffer with being sorted by an incoming path via which the received data is received, and the common buffer is used virtually as individual buffers. In addition, another conventional technique has been proposed in which a number N of input buffers and one common buffer are prepared, and when an available space of the common buffer is equal to or larger than a space needed for the number N of packets, a space for storing packets are changed from the input buffers to the common buffer so that a tolerance to the bursty arrival of packets is ensured.
Japanese Laid-open Patent Publication Nos. 11-32055 and 7-107116 disclose the related art.